package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_401_二进制手表 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_401_二进制手表().readBinaryWatch(1));
    }

    /**
     * 题目：二进制手表顶部有 4 个 LED 代表 小时（0-11），
     * 底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
     * 例如，下面的二进制手表读取 "3:25" 。
     *
     * 小时不会以零开头：
     * 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
     *
     * 分钟必须由两位数组成，可能会以零开头：
     * 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。
     *
     * 分析：
     *      1.区分  小时、分钟
     *
     * 边界值 & 注意点：
     *      1.
     **/
    List<String> ans=new ArrayList<>();
    int[] a=new int[]{1,2,4,8,1,2,4,8,16,32};
    public List<String> readBinaryWatch(int num) {
        dfs(num,0,0,0);
        return ans;
    }
    /**
     * Description: 递归结构:我先选出一个数字,剩下的选择方案交给递归
     *                       r(n)=r(n-1)+w
     * @param cnt 亮灯的个数
     * @param h 当前已累积小时值
     * @param m 当前已累积分钟值
     * @param idx 开始选择数据灯的下标
     */
    void dfs(int cnt,int h,int m,int idx){
        if(cnt==0)ans.add(h+":"+(m>9?m:"0"+m));
        for(int i=idx;i<10&&cnt>0;i++){
            if(i<4&&h+a[i]<12)dfs(cnt-1,h+a[i],m,i+1);
            if(i>=4&&m+a[i]<60)dfs(cnt-1,h,m+a[i],i+1);
        }
    }
}
